// https://leetcode-cn.com/problems/path-sum-iii/
// 437. Path Sum III
// Given the root of a binary tree and an integer targetSum, return
// the number of paths where the sum of the values along the path
// equals targetSum.
// The path does not need to start or end at the root or a leaf, but it must
// go downwards (i.e., traveling only from parent nodes to child nodes)
var pathSum = function(root, targetSum) {
    const prefix = new Map();
    prefix.set(0, 1);
    return dfs(root, prefix, 0, targetSum);
}

function dfs(root, prefix, curr, targetSum) {
    if (root === null) return 0;

    let ret = 0;
    curr += root.val;

    ret = prefix.get(curr - targetSum) || 0;
    prefix.set(curr, (prefix.get(curr) || 0) + 1);
    ret += dfs(root.left, prefix, curr, targetSum);
    ret += dfs(root.right, prefix, curr, targetSum);
    prefix.set(curr, (prefix.get(curr) || 0) - 1);

    return ret;
}
